<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Title</title>
</head>
<body>
<script>
	const arr = [23, 4, 5, 76, 99, 38, 56, 90]

	function swap(arr, a, b) {
		arr[a] = arr[a] ^ arr[b]
		arr[b] = arr[a] ^ arr[b]
		arr[a] = arr[a] ^ arr[b]
	}
</script>
<script>
	// O(n方)
	function bubble(arr) {
		const len = arr.length
		if (len <= 1) return arr

		for (let i = 0; i < len; i++) {
			for (let j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j + 1)
				}
			}
		}

		return arr
	}

	// O(n方)
	function selectSort (arr) {
		const len = arr.length
		if (len <= 1) return arr

		let min
		for (let i = 0; i < len; i ++) {
			min = i
			for (let j = i + 1; j < len; j ++) {
				if (arr[j] < arr[min]) {
					min = j
				}
			}

			if (min !== i) {
				swap(arr, min, i)
			}
		}

		return arr
	}

	// O(n) - O(n方)
	function insertSort (arr) {
		const len = arr.length
		if (len <= 1) return arr

		let temp
		for (let i = 1; i < len; i ++) {
			temp = arr[i]
			let j = i
			while (j > 0 && arr[j - 1] > temp) {
				arr[j] = arr[j - 1]
				j --
			}
			arr[j] = temp
		}

		return arr
	}

	{
		// O(nlogn)
		function mergeSort (arr) {
			const len = arr.length
			if (len <= 1) return arr

			const mid = len / 2 | 0
			const left = mergeSort(arr.slice(0, mid))
			const right = mergeSort(arr.slice(mid))

			return merge(left, right)
		}

		function merge (left, right) {
			let i = 0
			let j = 0
			const rst = []
			while (i < left.length && j < right.length) {
				rst.push(left[i] < right[j] ? left[i ++] : right[j ++])
			}
			return rst.concat(i < left.length ? left.slice(i) : right.slice(j))
		}

		console.log(mergeSort(arr))
	}

	// O(nlogn)
	function quickSort (arr) {
		if (arr.length <= 1) return arr

		const temp = arr[0]
		arr = arr.slice(1)
		const left = []
		const right = []
		for (let i = 0; i < arr.length; i ++) {
			if (arr[i] < temp) {
				left.push(arr[i])
			} else {
				right.push(arr[i])
			}
		}
		return quickSort(left).concat(temp).concat(quickSort(right))
	}

	// O(n)
	function countSort (arr) {
		const len = arr.length
		if (len <= 1) return arr

		const max = Math.max(...arr)
		const newArr = new Array(max + 1)

		for (let i = 0; i < len; i ++) {
			if (newArr[arr[i]]) {
				newArr[arr[i]] ++
			} else {
				newArr[arr[i]] = 1
			}
		}

		const rst = []
		newArr.forEach((count, index) => {
			while (count >= 1) {
				rst.push(index)
				count --
			}
		})

		return rst
	}

	{
		// O(n+k)
		function bucketSort (arr, bucketSize = 3) {
			const len = arr.length
			if (len <= 1) return arr

			const buckets = createBuckets(arr, bucketSize)
			let rst = []
			for (const bucket of buckets) {
				rst = rst.concat(insertSort(bucket))
			}

			return rst
		}

		function createBuckets (arr, bucketSize) {
			const min = Math.min(...arr)
			const max = Math.max(...arr)
			const count = ((max - min) / bucketSize | 0) + 1
			const buckets = [...new Array(count)].map(() => [])
			for (let i = 0; i < arr.length; i ++) {
				const index = ((arr[i] - min) / bucketSize) | 0
				buckets[index].push(arr[i])
			}
			return buckets
		}

		function insertSort (arr) {
			const len = arr.length
			if (len <= 1) return arr

			let temp
			for (let i = 1; i < len; i ++) {
				temp = arr[i]
				let j = i
				while (j > 0 && arr[j - 1] > temp) {
					arr[j] = arr[j - 1]
					j --
				}
				arr[j] = temp
			}

			return arr
		}

		console.log(bucketSort(arr))
	}

	// O(nk)
	function radixSort (arr) {
		const len = arr.length
		if (len <= 1) return arr

		const max = Math.max(...arr)
		const base = 10
		let division = 1
		while (division <= max) {
			const buckets = [...Array(base)].map(() => [])
			for (let i = 0; i < len; i ++) {
				const index = ((arr[i] / division) | 0 ) % base
				buckets[index].push(arr[i])
			}
			arr = [].concat(...buckets)

			division *= base
		}

		return arr
	}


	console.log(radixSort(arr))
</script>
</body>
</html>
